import collections
from typing import List


class Solution:
    def minTrioDegree(self, n: int, edges: List[List[int]]) -> int:
        # 生成无向图的邻接列表结构
        graph = collections.defaultdict(set)  # 每个点只记录比它下标大的邻边（用于遍历三角形）
        count = collections.Counter()  # 用于计算度数
        for n1, n2 in edges:
            if n1 > n2:
                n1, n2 = n2, n1
            graph[n1].add(n2)
            count[n1] += 1
            count[n2] += 1

        ans = float("inf")

        # 遍历图中所有三角形
        for i in range(n):  # 遍历所有顶点
            for j in graph[i]:  # 遍历顶点的邻边的顶点（根据无向图的性质，有:i<j)
                for k in list(graph[i] & graph[j]):  # 遍历所有与i和j能构成三角形的点（根据无向图的性质，有:i<j<k)
                    ans = min(ans, count[i] + count[j] + count[k] - 6)

        return ans if ans != float("inf") else -1


if __name__ == "__main__":
    print(Solution().minTrioDegree(n=6, edges=[[1, 2], [1, 3], [3, 2], [4, 1], [5, 2], [3, 6]]))  # 3
    print(Solution().minTrioDegree(n=7, edges=[[1, 3], [4, 1], [4, 3], [2, 5], [5, 6], [6, 7], [7, 5], [2, 6]]))  # 0
